101

8.5

Exercises for Chap. 8

Task 8.1

How much does the computation time increase with different algorithms?

Compare the RNA folding algorithm RNAfold, a BLAST search, and protein folding.

With BLAST, also try to clarify at the same time how the E-value moves favorably down­

ward, to smaller values, with a smaller database.

Just try out the different calculation times with your own test examples.

Task 8.2

So how do you deal with the hard problems that biological systems present you with?

Please list some different search strategies that you have learned about in the book or that

you can think of (don’t worry, the best ones will be discussed in a moment).

Task 8.3

What general search strategies for complex problems in bioinformatics do you know?

Task 8.4

Explain what is meant by NP-problems or P-problems in bioinformatics? How is a diffi­

cult computational problem defined informatically? Make this clear with an example.

Useful Tools and Web Links

https://baba.sourceforge.net

• Here basic algorithms of bioinformatics like local and global alignment are

presented very nicely and exemplarily.

https://discrete.gr/complexity/

• This page gives a nice introduction to computing complexity.

Turing machine:

https://www.alanturing.net/turing_archive/pages/reference%20articles/

what%20is%20a%20turing%20machine.html

• There are many representations of this, but this one is right on the Turing net­

work and descriptive.

NP problems pitfalls:

https://www.win.tue.nl/~gwoegi/P-­versus-­NP.htm

• This page shows a bit of how not to do it (or how easy it is to fail at this prob­

lem). For solid work, see Aaranson 2003, 2005, respectively.

Introduction to parallel programming (for time-consuming calculations):

Parallel Programming with C+ + :

https://gridgroup.hefr.ch/popc/doku.php

Message Passing Interface (MPI):

Parallelization (Introduction to parallel programming)

https://mpitutorial.com/tutorials/mpi-­introduction/

8.5  Exercises for Chap. 8